﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution131
{
    IList<IList<string>> res=new List<IList<string>>();
    public IList<IList<string>> Partition(string s)
    {

        IList<string> childStrs=new List<string>();
        DFS(s, 0, childStrs);

        return res;

    }

    private void DFS(string s, int startIndex, IList<string> childStrs)
    {


        if (startIndex == s.Length)
        {
            res.Add(new List<string>(childStrs));
        }

        for(int i = startIndex; i < s.Length; i++)
        {

            string childStr =s.Substring(startIndex, i - startIndex+1);
            //判断回文
            if(huiwen(childStr))
            {
                childStrs.Add(childStr);
                DFS(s, i + 1, childStrs);
                childStrs.RemoveAt(childStrs.Count - 1);
            }
            else
            {
                continue;//ef不是回文，继续判断而不是返回 
                //return;//使用return会导致efe不通过
            }

            
        }
    }

    private bool huiwen(string s)
    {

        //
        int left = 0;
        int right =s.Length-1;
        while(left < right)
        {
            if (s[left] == s[right])
            {
                left++;
                right--;
            }
            else
            {
                return false;
            }

        }
        return true;

    }
}

class Program131
{

    static void Main131(string[] args)
    {
        Solution131 solution131 = new Solution131();
        string s = "efe";

        IList<IList<string>> res= solution131.Partition(s);
        for (int i = 0; i < res.Count; i++)
        {

            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();
        }
    }
    
}
